\subsection{Descripcion}

En esta secci\'{o}n describiremos el algoritmo para aplicar el filtro cropflip a una imagen mediante el uso de instrucciones SIMD. La descripci\'{o}n 
matem\'{a}tica de dicho filtro viene dada por la siguiente f\'{o}rmula:
\begin{equation*}
 dst(i,j) = src(tamy+offsety-i-1,offsetx+j)
\end{equation*}

El efecto ser\'a el siguiente: recortar un rect\'angulo de dimensiones $tamx * tamy$, a partir de la columna $offsetx$, fila $offsety$, y pegarlo,
volteado horizontalmente, en la imagen destino (l\'ogicamente, la imagen destino ser\'a de dimensiones $tamx * tamy$). As\'i, la imagen fuente
nos queda interpretada, en funci\'on de los par\'ametros, seg\'un indica la figura 1:

\begin{figure}[H]
    \begin{center}
    \includegraphics[width=70mm,scale=0.75]{diagrama1.png}
    \caption{Imagen fuente}
    \end{center}
  \label{cropflip13c}
\end{figure}
 
Para operar con las im\'agenes, contamos con los punteros $src$ y $dst$, que apuntan, respectivamente, al primer p\'ixel de las im\'agenes fuente y destino.
Para operar con la regi\'on cuadriculada (que ser\'a la \'unica con la que debe operar el algoritmo) debemos, en primer lugar, avanzar el puntero $src$ al primer
p\'ixel de la zona cuadriculada: lograremos esto increment\'andolo, en $(offsety * src_row_size) + offsetx$.

Teniendo esto, como el algoritmo debe voltear horizontalmente la zona cuadriculada de la imagen fuente, optamos por recorrer la imagen destino en orden reverso
respecto de las filas; esto es, recorreremos las filas de la imagen destino de abajo hacia arriba. Como la orientaci\'on horizontal debe preservarse, recorreremos
cada fila de la imagen destino de la misma manera que recorreremos las filas de la imagen fuente (\'unicamente de la zona cuadriculada): de izquierda a derecha.
Luego, el algoritmo para este filtro es bastante sencillo: leeremos 4 p\'ixeles de la imagen fuente y los escribiremos en la imagen destino, sin ning\'un tipo 
de procesamiento; al llegar al fin de una fila, deberemos incrementar el puntero sobre la imagen fuente (para bajar a la fila siguiente) en 
$src_row_size - tamx - offsetx$ bytes, para pasar a la fila siguiente de la zona cuadriculada. An\'alogamente, debemos decrementar (para subir de fila) 
el puntero sobre la imagen destino en $dst_row_size - tamx$ bytes.

 
\subsection{Experimentacion}

\subsubsection{Analisis del codigo generado}

En este experimento analizaremos el c\'{o}digo generado por la herramienta objdump aplicada sobre el archivo cropflip$\textunderscore$c.o, tomando como
gu\'{i}a las preguntas formuladas por la c\'{a}tedra en el enunciado.

En cuanto a la existencia de otras funciones aparte de cropflip$\textunderscore$c, nuestra impresi\'{o}n inicial indicaba que muchas de las otras funciones 
aparecen en el c\'{o}digo ensamblado con el objetivo de proveer informaci\'{o}n \'{u}til para debuggear el programa encargado de aplicar el filtro. Se nos
ocurri\'{o} que esto era as\'{i}, principalmente, por los nombres de las funciones generadas: debug$\textunderscore$info, debug$\textunderscore$abbrev y 
debug$\textunderscore$loc son algunos ejemplos. En efecto, pudimos corroborar nuestra impresi\'{o}n removiendo el flag -ggdb del Makefile, volviendo a compilar
y a generar el c\'{o}digo ensamblado, pues las funciones listadas anteriormente ya no estaban en dicho c\'{o}digo.

En cuanto a la manipulaci\'{o}n de las variables, observamos en el c\'{o}digo generado que las variables locales est\'{a}n definidas en el stack, con lo cual
un acceso a cualquiera de ellas (una lectura o una escritura) significa un acceso a memoria. Observamos que una optimizaci\'{o}n posible para este c\'{o}digo
es la de usar registros de prop\'{o}sito general para las variables locales al programa en vez de usar la pila, pues acceder a dichos registros es m\'{a}s 
r\'{a}pido que un acceso a la memoria.

\subsubsection{Optimizaciones del compilador}

En este experimento haremos un an\'{a}lisis an\'{a}logo al del punto anterior, pero compilando el c\'{o}digo de C con el flag -O1.

En primer lugar, observamos que el c\'{o}digo de la funci\'{o}n \verb|cropflip_c| empieza con pushes de algunos registros de prop\'{o}sito general
(\verb|r12|, \verb|r13|), para luego usarlos como variables en dicha funci\'{o}n, lo cual ayuda a reducir la cantidad de instrucciones donde se direccione a memoria.
Para ver qu\'{e} flags brinda el compilador para optimizar el c\'{o}digo, ejecutamos en la terminal \verb|man gcc| y a modo de ejemplo, mencionaremos 3 de ellos:
\verb|-O1|, \verb|-Ofast|, \verb|-Os|. Por \'{u}ltimo, mencionaremos 3 optimizaciones que hace el gcc sobre el c\'{o}digo: \verb|-falign_jumps|,
\verb|-falign_labels|, \verb|-fbranch_probabilities|.



\subsubsection{Calidad de la mediciones}

Para llevar a cabo este experimento decidimos que, al tener como eje la calidad de las observaciones al medir el tiempo de ejecuci\'on del filtro,
deb\'iamos considerar, en todos los incisos, la misma imagen de prueba (y los mismos valores para $tamx$, $tamy$, $offsetx$ y $offsety$) en todas las 
mediciones tomadas, para poder mostrar mejor c\'omo var\'ian el tiempo de ejecuci\'on, la media y la varianza al variar solamente los recaudos num\'ericos 
tomados sobre las observaciones (descartar o no los outliers, considerar lo que ocurre con programas corriendo en simult\'aneo con la ejecuci\'on del filtro), y
dejar fijos los par\'ametros de entrada del programa. Con esto en mente, tomamos como caso de prueba para este ejercicio la imagen ``$lena.512x512.bmp$'', y 
los siguientes valores para los par\'ametros espec\'ficos de este filtro: $tamx = 180$, $tamy = 190$, $offsetx = 0$ y $offsety = 0$.

Adicionalmente, decidimos considerar, para cada medici\'on individual (esto es, para una ejecuci\'on cualquiera del filtro sobre la imagen), el tiempo empleado
para aplicar 10 veces el filtro sobre la imagen. Para dejar en claro esto, incluiremos la porci\'on de c\'odigo que mide los tiempos de ejecuci\'on:

\begin{codesnippet}
\begin{verbatim}
for(i=0;i<10;i++){
  MEDIR_TIEMPO_START(start);
  for(j=0;j<10;j++){
    cropflip(info.bytes, config->dst.bytes, info.width, info.height, info.width_with_padding,
    config->dst.width_with_padding, extra->tamx, extra->tamy, extra->offsetx, extra->offsety);
  }   
  MEDIR_TIEMPO_STOP(end);
  mediciones[i] = end-start;
}
\end{verbatim} 
\end{codesnippet}

donde $mediciones$ es un arreglo de 10 posiciones que almacenar\'a el tiempo de la ejecuci\'on i\'esima. Tomamos esta decisi\'on bas\'andonos en c\'omo
(creemos que) funciona el scheduler del sistema operativo: si recorre circularmente las tareas activas, asign\'andole a cada una cantidad de tiempo,
pod\'ia darse el caso en que el programa encargado de aplicar el filtro terminara en la ``primera vuelta'' (es decir, necesitara menos tiempo para 
aplicar el filtro que el quantum que le fue asignado), con lo cual el efecto del loop infinito corriendo de fondo podr\'ia no apreciarse en absoluto.



Este gr\'{a}fico fue hecho con mediciones tomadas al correr el filtro $cropflip$ para generar im\'{a}genes de 200 x 170 p\'{i}xeles.
\begin{figure}[H]
    \includegraphics[width=1\textwidth]{cropflip13c}
  \label{cropflip13c}
\end{figure}

En el gr\'{a}fico podemos observar que las mediciones tomadas mientras se utilizan los cores logicos no tienen coherencia. Lo esperado en este experimento es 
que, aunque el proceso tarde m\'{a}s ciclos de clock, se mantenga la proporci\'{o}n entre tama\~{n}o y ciclos de clock. Sin embargo, eso no es lo que muestran las 
mediciones, pues la varianza toma valores muy altos y al compararlo con los resultados obtenidos en las mediciones sin uso de los cores, concluimos que la calidad
de las mediciones tomadas con el uso de los cores es demasiado pobre, por lo que debemos mejorarla de alg\'{u}n modo.
 
A continuaci\'{o}n, mostramos un gr\'{a}fico que compara la calidad de las mediciones al usar los datos sin ninguna modificaci\'{o}n 
versus la informaci\'{o}n de las mismas mediciones, pero con los outliers descartados, en un intento por mejorarlas. 

\begin{figure}[H]
    \includegraphics[width=1\textwidth]{cropflip13d}
  \label{cropflip13d}
\end{figure}

Aqu\'{i} vemos que la varianza se reduce y que la diferencia entre casos es menor que en caso anterior. Podemos observar de este modo que la calidad de las mediciones
mejora. Creemos que si se incrementa la cantidad de mediciones, manteniendo la propocion de outliers descartados, la calidad mejorar\'{a} a\'{u}n m\'{a}s. 

\subsubsection{Secuencial vs. Vectorial}

En este experimento queremos comprobar emp\'{i}ricamente la utilidad de usar SSE. Es decir, queremos comprobar si, para este tipo de filtro, logramos una 
performance mejor a aquellas obtenidas de optimizaciones de c\'{o}digo en lenguaje C.

\begin{figure}[H]
    \includegraphics[width=1\textwidth]{cropflip14}
  \label{cropflip14}
\end{figure}

Podemos observar que, si bien la  performance del c\'{o}digo sin optimizacion es radicalmente mala, con solo una optimizaci\'{o}n simple (-O2 en adelante),
 el c\'{o}digo C obtiene una performance incluso mejor que la de Assembler usando SSE. Esto que nos lleva a concluir que para este tipo de procesamiento de datos, 
 usar codigo Assembler no nos reporta ning\'{u}n beneficio, y de hecho nos prejudica, pues perdemos claridad y tardamos mas en escribir el c\'{o}digo, arriesgandonos 
 a tener serios problemas de memoria, problemas que en la mayoria de los casos, no tendr\'{i}amos en lenguaje C.
 
 Como aclaraci\'{o}n final para la discusi\'{o}n de estos resultados, si bien vemos en los gr\'{a}ficos que, al optimizar la versi\'{o}n en C, se obtienen
 mejores resultados que con la de Assembler, nuestra intuici\'{o}n indicaba que la versi\'{o}n en Assembler deb\'{i}a funcionar mejor que la de C, incluso 
 usando el flag -O3, y si bien, por lo acotado del tiempo para el trabajo, no hemos podido analizar exhaustivamente el codigo generado por la herramienta
 objdump para la versi\'{o}n de cropflip\textunderscore c.o tras compilar con la optimizaci\'{o}n -O3, creemos que dicha versi\'{o}n podr\'{i}a estar
 utilizando mejoras como, por ejemplo, la de loop unrolling, para ejecutar varias iteraciones del filtro en una sola pasada.

\subsubsection{CPU vs. Bus de memoria}

En este experimento intentamos determinar cu\'{a}l es el factor limitante para la performance del filtro. Por lo tanto, tomamos mediciones para las mismas 
im\'{a}genes agregando distintos tipos de instruciones de operaciones aritm\'{e}ticas y accesos a memoria para lograr una variaci\'{o}n en la performance que
nos permita decidir qu\'{e} tipo de instrucciones es el que influye de mayor manera en el tiempo de ejecuci\'{o}n.

\begin{figure}[H]
    \includegraphics[width=1\textwidth]{cropflip15}
  \label{cropflip14}
\end{figure}

Vemos que este gr\'{a}fico presenta variaciones en el tiempo de ejecucion para cualquier instruccion agregada. Si bien en principio no parecen diferir en mucho 
las versiones con la misma cantidad de instrucciones aritm\'{e}ticas y accesos a memoria, podemos notar que a medida que se incrementa la catidad de las mismas, 
los accesos a memoria son los que mas entorpecen la performance, es decir, que los accesos a memoria limitan m\'{a}s que las instrucciones aritm\'{e}ticas.
